﻿namespace AdvancedTraining.Lesson51;

/// <summary>
/// 设计搜索自动补全系统 - LeetCode 642
/// 使用前缀树和有序集合实现搜索自动补全功能
/// </summary>
public class DesignSearchAutocompleteSystem //leetcode_0642
{
    /// <summary>
    /// 自动补全系统实现类
    /// 算法思路：前缀树 + 有序集合
    /// 1. 使用前缀树存储所有输入的历史记录
    /// 2. 每个前缀树节点维护一个有序集合，存储以该前缀开头的热门单词
    /// 3. 有序集合按次数降序、字典序升序排列
    /// 4. 输入时实时更新前缀树和有序集合
    /// 时间复杂度：初始化O(N*L)，输入O(L+logM)，其中N为句子数，L为平均长度，M为候选数
    /// 空间复杂度：O(N*L)，存储前缀树和相关数据结构
    /// </summary>
    public class AutocompleteSystem
    {
        // 题目的要求，只输出排名前3的列表
        private readonly int top = 3;
        private TrieNode cur;

        // 某个前缀树节点，上面的有序表，不在这个节点内部
        // 外挂
        public Dictionary<TrieNode, SortedSet<WordCount>> nodeRankMap = new();

        public string path = "";
        public TrieNode root;

        // 字符串 "abc"  7次   ->  ("abc", 7)
        public Dictionary<string, WordCount> wordCountMap = new();

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="sentences">历史句子数组</param>
        /// <param name="times">对应的出现次数数组</param>
        public AutocompleteSystem(string[] sentences, int[] times)
        {
            root = new TrieNode(null, "");
            path = "";
            cur = root;
            for (var i = 0; i < sentences.Length; i++)
            {
                var word = sentences[i];
                var count = times[i];
                var wc = new WordCount(word, count - 1);
                wordCountMap[word] = wc;
                foreach (var c in word) Input(c);
                Input('#');
            }
        }

        // ' ' -> 0
        // 'a' -> 1
        // 'b' -> 2
        // ...
        // 'z' -> 26
        //  '`'  a b  .. z
        private int F(char c)
        {
            return c == ' ' ? 0 : c - '`';
        }

        /// <summary>
        /// 输入字符并返回自动补全结果
        /// </summary>
        /// <param name="c">输入的字符</param>
        /// <returns>自动补全结果列表</returns>
        public IList<string> Input(char c)
        {
            IList<string> ans = new List<string>();
            if (c != '#')
            {
                path += c;
                var i = F(c);
                if (cur.nexts[i] == null) cur.nexts[i] = new TrieNode(cur, path);
                cur = cur.nexts[i];
                if (!nodeRankMap.ContainsKey(cur)) nodeRankMap[cur] = new SortedSet<WordCount>();
                var k = 0;
                // for循环本身就是根据排序后的顺序来遍历！
                foreach (var wc in nodeRankMap[cur])
                {
                    if (k == top) break;
                    ans.Add(wc.word);
                    k++;
                }
            }

            // c = #   path = "abcde"
            // #
            // #
            // #
            // a b .. #
            if (c == '#' && !path.Equals(""))
            {
                // 真的有一个，有效字符串需要加入！path
                if (!wordCountMap.ContainsKey(path)) wordCountMap[path] = new WordCount(path, 0);
                // 有序表内部的小对象，该小对象参与排序的指标数据改变
                // 但是有序表并不会自动刷新
                // 所以，删掉老的，加新的！
                var oldOne = wordCountMap[path];
                var newOne = new WordCount(path, oldOne.count + 1);
                while (cur != root)
                {
                    nodeRankMap[cur].Remove(oldOne);
                    nodeRankMap[cur].Add(newOne);
                    cur = cur.father;
                }

                wordCountMap[path] = newOne;
                path = "";
                // cur 回到头了
            }

            return ans;
        }

        /// <summary>
        /// 前缀树节点类
        /// </summary>
        public class TrieNode
        {
            public TrieNode father;
            public TrieNode[] nexts;
            public string path;

            public TrieNode(TrieNode f, string p)
            {
                father = f;
                path = p;
                nexts = new TrieNode[27];
            }
        }

        /// <summary>
        /// 单词计数类，用于排序
        /// </summary>
        public class WordCount : IComparable<WordCount>
        {
            public int count;
            public string word;

            public WordCount(string w, int c)
            {
                word = w;
                count = c;
            }

            public int CompareTo(WordCount o)
            {
                return count != o.count ? o.count - count : word.CompareTo(o.word);
            }
        }
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 设计搜索自动补全系统测试 ===");

        // 测试用例1: 基本功能测试
        Test1();

        // 测试用例2: 相同前缀不同热度
        Test2();

        // 测试用例3: 空输入历史
        Test3();

        // 测试用例4: 复杂场景
        Test4();

        // 测试用例5: 空格处理
        Test5();

        Console.WriteLine("\n=== 算法说明 ===");
        Console.WriteLine("前缀树：存储所有输入历史，支持快速前缀匹配");
        Console.WriteLine("有序集合：每个前缀节点维护热门单词列表，按热度排序");
        Console.WriteLine("实时更新：输入时动态更新统计信息和排序结果");
        Console.WriteLine("时间复杂度：初始化O(N*L)，输入O(L+logM)");
        Console.WriteLine("空间复杂度：O(N*L)");
    }

    /// <summary>
    /// 测试用例1: 基本功能测试
    /// </summary>
    private static void Test1()
    {
        Console.WriteLine("\n测试用例1: 基本功能测试");
        string[] sentences = ["i love you", "island", "ironman"];
        int[] times = [5, 3, 2];
        var system = new AutocompleteSystem(sentences, times);

        Console.WriteLine($"初始句子: [{string.Join(", ", sentences)}]");
        Console.WriteLine($"出现次数: [{string.Join(", ", times)}]");

        var result1 = system.Input('i');
        Console.WriteLine($"输入 'i': [{string.Join(", ", result1)}]");

        var result2 = system.Input(' ');
        Console.WriteLine($"输入 ' ': [{string.Join(", ", result2)}]");

        var result3 = system.Input('a');
        Console.WriteLine($"输入 'a': [{string.Join(", ", result3)}]");

        var result4 = system.Input('#');
        Console.WriteLine($"输入 '#': [{string.Join(", ", result4)}]");
    }

    /// <summary>
    /// 测试用例2: 相同前缀不同热度
    /// </summary>
    private static void Test2()
    {
        Console.WriteLine("\n测试用例2: 相同前缀不同热度");
        string[] sentences = ["abc", "abd", "abf"];
        int[] times = [3, 2, 1];
        var system = new AutocompleteSystem(sentences, times);

        Console.WriteLine($"初始句子: [{string.Join(", ", sentences)}]");
        Console.WriteLine($"出现次数: [{string.Join(", ", times)}]");

        var result1 = system.Input('a');
        Console.WriteLine($"输入 'a': [{string.Join(", ", result1)}]");

        var result2 = system.Input('b');
        Console.WriteLine($"输入 'b': [{string.Join(", ", result2)}]");
    }

    /// <summary>
    /// 测试用例3: 空输入历史
    /// </summary>
    private static void Test3()
    {
        Console.WriteLine("\n测试用例3: 空输入历史");
        string[] sentences = [];
        int[] times = [];
        var system = new AutocompleteSystem(sentences, times);

        Console.WriteLine("初始句子: []");
        Console.WriteLine("出现次数: []");

        var result1 = system.Input('h');
        Console.WriteLine($"输入 'h': [{string.Join(", ", result1)}]");

        var result2 = system.Input('e');
        Console.WriteLine($"输入 'e': [{string.Join(", ", result1)}]");

        var result3 = system.Input('#');
        Console.WriteLine($"输入 '#': [{string.Join(", ", result3)}]");

        var result4 = system.Input('h');
        Console.WriteLine($"输入 'h': [{string.Join(", ", result4)}]");
    }

    /// <summary>
    /// 测试用例4: 复杂场景
    /// </summary>
    private static void Test4()
    {
        Console.WriteLine("\n测试用例4: 复杂场景");
        string[] sentences = ["i love you", "island", "ironman", "i love leetcode"];
        int[] times = [5, 3, 2, 2];
        var system = new AutocompleteSystem(sentences, times);

        Console.WriteLine($"初始句子: [{string.Join(", ", sentences)}]");
        Console.WriteLine($"出现次数: [{string.Join(", ", times)}]");

        var result1 = system.Input('i');
        Console.WriteLine($"输入 'i': [{string.Join(", ", result1)}]");

        var result2 = system.Input(' ');
        Console.WriteLine($"输入 ' ': [{string.Join(", ", result2)}]");

        var result3 = system.Input('a');
        Console.WriteLine($"输入 'a': [{string.Join(", ", result3)}]");

        var result4 = system.Input('#');
        Console.WriteLine($"输入 '#': [{string.Join(", ", result4)}]");

        var result5 = system.Input('i');
        Console.WriteLine($"输入 'i': [{string.Join(", ", result5)}]");

        var result6 = system.Input(' ');
        Console.WriteLine($"输入 ' ': [{string.Join(", ", result6)}]");
    }

    /// <summary>
    /// 测试用例5: 空格处理
    /// </summary>
    private static void Test5()
    {
        Console.WriteLine("\n测试用例5: 空格处理");
        string[] sentences = ["hello world", "hello there"];
        int[] times = [3, 2];
        var system = new AutocompleteSystem(sentences, times);

        Console.WriteLine($"初始句子: [{string.Join(", ", sentences)}]");
        Console.WriteLine($"出现次数: [{string.Join(", ", times)}]");

        var result1 = system.Input('h');
        Console.WriteLine($"输入 'h': [{string.Join(", ", result1)}]");

        var result2 = system.Input('e');
        Console.WriteLine($"输入 'e': [{string.Join(", ", result2)}]");

        var result3 = system.Input('l');
        Console.WriteLine($"输入 'l': [{string.Join(", ", result3)}]");

        var result4 = system.Input('l');
        Console.WriteLine($"输入 'l': [{string.Join(", ", result4)}]");

        var result5 = system.Input('o');
        Console.WriteLine($"输入 'o': [{string.Join(", ", result5)}]");

        var result6 = system.Input(' ');
        Console.WriteLine($"输入 ' ': [{string.Join(", ", result6)}]");
    }
}